package leetcode.array_sort.movewindow;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * <p>
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 分析思路：首先我们需要判断重复字符，当然不能再此将子数组进行循环遍历看有没有出现了，可以开辟一个新的空间 int[256]
 * 将字符串转成字符数组  在 char[l,r]上进行判断，++r上的元素不是重复元素， 指针向下移 如果是 找到前一个重复元素 i 指向他，每次操作都要记录响应的频率
 * 判断是否重复可以在O(1)级别解决； 时间复杂度为O(n);
 * <p>
 * 滑窗总结：定义两个指针，使得满足定义，在满足条件下进行移动指针，当然在使用数组的时候需要判断数组越界情况。
 */
public class Solution3 {
    public static int lengthOfLongestSubstring(String s) {
        int[] charFreq = new int[256];
        int l = 0;
        int r = -1;// arr[l,r]为空，开始时候滑动窗口大小为0；我们尝试不断扩大r的值，使得其满足条件 滑动窗口为 arr[l,r]
        int res = 0;
        while (l < s.length()) {
            //尝试去增加r
            if (r + 1 < s.length() && charFreq[s.charAt(r + 1)] == 0) {//当r+1位置元素的频率为0时，说明还没有重复元素
                //对r++; 跟新r++字符频率
                r++;
                charFreq[s.charAt(r)] = charFreq[s.charAt(r)] + 1;
                //计算长度
                res = Math.max(res, r - l + 1);
            } else {//r ==s.length-1 或者 charFreq[s.charAt(r + 1)] > 0  移动 l  其实当r ==s.length-1 时没有必要在移动l了
                //使当前元素的频率减一
                charFreq[s.charAt(l)] = charFreq[s.charAt(l)] - 1;
                l++;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }
}
